Numeral-P-completo


Numeral-P-completo
En teoría de la complejidad computacional, la clase de complejidad \#P-completo (se pronuncia numeral-P-completo) es el conjunto de los problemas de conteo que pertenecen a \#P tales que todo problema de \#P se puede reducir en todos los de $P-completo en tiempo polinómico. Algunos ejemplos de \#P-completo incluyen: ● ¿Cuantas asignaciones de variables satisfacen una fórmula dada? ● ¿Cuantas correspondencias perfectas hay en un grafo bipartito? Se piensa que no hay algoritmos en tiempo polinómico para resolver problemas \#P-completos. Inclusive, no se conocen algoritmos deterministas que puedan dar una solución aproximada de calidad razonable.

Enciclopedia Universal. 2012.

Mira otros diccionarios:

  • Numeral-P-completo — En teoría de la complejidad computacional, la clase de complejidad #P completo (se pronuncia numeral P completo) es el conjunto de los problemas de conteo que pertenecen a #P tales que todo problema de #P se puede reducir en todos los de $P… …   Wikipedia Español

  • Numeral-P — En teoría de la complejidad computacional, la clase de complejidad #P (pronunciado numeral P) es el conjunto de los problemas de conteo asociados a los problemas de decisión en el conjunto NP. Un problema en NP se describe usualmente con la… …   Wikipedia Español

  • Leslie Valiant — Leslie Gabriel Valiant (nacido el 28 de marzo de 1949) es un informático teórico británico. Educado en el King s College, Cambridge, Imperial College London y la Universidad de Warwick donde recibió su Ph.D. en ciencias de computación en 1974.… …   Wikipedia Español

  • Teoremas de incompletitud de Gödel — Kurt Gödel a los 19 años de edad, cinco años antes de la demostración de los teoremas. Los teoremas de incompletitud de Gödel son dos célebres teoremas de lógica matemática demostrados por Kurt Gödel en 1930. Ambos están relacionados con la… …   Wikipedia Español

  • Nombre — (Del lat. numen.) ► sustantivo masculino 1 Palabra que designa los objetos físicos, síquicos o ideales: ■ la esperanza es el nombre de una virtud teologal. 2 Término o conjunto de ellos con que se designa a una persona: ■ su nombre es Juan;… …   Enciclopedia Universal

  • Septuaginta — Columna en caracteres unciales de los textos de Esdras, tal como se les lee en la Biblia Septuaginta. La Biblia griega, comúnmente llamada Biblia Septuaginta o Biblia de los Setenta, y generalmente abreviada simplemente LXX, fue traducida de… …   Wikipedia Español

  • Francisco Domínguez Brito — Saltar a navegación, búsqueda Francisco Domínguez Brito …   Wikipedia Español

  • medio — (Del lat. medius.) ► adjetivo 1 Que es igual a la mitad de un todo o de un entero: ■ se bebió media botella de vino; ya he leído medio libro; con media docena de huevos es suficiente. 2 Que está aproximadamente entre dos extremos: ■ pertenece a… …   Enciclopedia Universal

  • Nomenclatura de hidrocarburos acíclicos — La Nomenclatura de Hidrocarburos Acíclicos es una metodología establecida para denominar y agrupar los hidrocarburos cuyas cadenas principales o secundarias son todas abiertas. Cuando todos los carbonos del compuesto tienen cuatro enlaces simples …   Wikipedia Español

  • Tarot (juego de cartas) — Para otros usos de este término, véase Tarot. El tarot es un juego de cartas que utiliza la baraja de tarot y se practica generalmente con cuatro jugadores aunque existen variantes desde dos hasta ocho jugadores. Este artículo comienza con la… …   Wikipedia Español


Compartir el artículo y extractos

Link directo
Do a right-click on the link above
and select “Copy Link”

We are using cookies for the best presentation of our site. Continuing to use this site, you agree with this.